package problem_everyday;

import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;

public class D2025_07_07_P1535 {
    /*
    * 给定一个[n][2]的数组，表示n个会议的开始日期和结束日期，每天可以参加一个会议，
    * 计算最多可以参加一个会议
    * */

    /*
    * 贪心：如果第i天可以参加多个会议，则应当选择参加结束时间最早的会议
    * 应此，我们实际上需要多次访问一个动态集合的最小值，可以使用最小堆结构
    * */

    public int maxEvents(int[][] events) {
        Arrays.sort(events, new Comparator<int[]>(){
            @Override
            public int compare(int[] a, int [] b){
                if(a[0] == b[0]){
                    return a[1] - b[1];
                }
                return a[0] - b[0];
            }
        });
        int day = events[0][0];
        int max_day = 0;
        for(int[] event: events){
            max_day = Math.max(event[1], max_day);
        }
        int res = 0;
        PriorityQueue<Integer> queue = new PriorityQueue<>();
        int i=0;
        while(day<=max_day){
            while(i<events.length && events[i][0] <= day){
                if(events[i][1] >= day) queue.add(events[i][1]);
                i++;
            }
            while(!queue.isEmpty() && queue.peek()<day){
                queue.poll();
            }
            if(!queue.isEmpty()){
                queue.poll();
                res ++;
            }
            day ++;

        }
        return res;
    }
}
